/*
 *
 * This is SGLIB version 1.0.3
 *
 * (C) by Marian Vittek, Bratislava, http://www.xref-tech.com/sglib, 2003-5
 *
 * License Conditions: You can use a verbatim copy (including this
 * copyright notice) of sglib freely in any project, commercial or not.
 * You can also use derivative forms freely under terms of Open Source
 * Software license or under terms of GNU Public License.  If you need
 * to use a derivative form in a commercial project, or you need sglib
 * under any other license conditions, contact the author.
 *
 *
 *
 */

#ifndef _SGLIB__h_
#define _SGLIB__h_

/* the assert is used exclusively to write unexpected error messages */
#include <assert.h>

/* ---------------------------------------------------------------------------- */
/* ---------------------------------------------------------------------------- */
/* -                            LEVEL - 0  INTERFACE                          - */
/* ---------------------------------------------------------------------------- */
/* ---------------------------------------------------------------------------- */

/* ---------------------------------------------------------------------------- */
/* ------------------------------ STATIC ARRAYS ------------------------------- */
/* ---------------------------------------------------------------------------- */

/*
 *
 * Basic algorithms  for sorting arrays. Multiple  depending arrays can
 * be rearranged using user defined 'elem_exchangers'
 *
 */

/*               HEAP - SORT  (level 0)           */

#define SGLIB_ARRAY_SINGLE_HEAP_SORT( type, a, max, \
                                      comparator )                     { \
        SGLIB_ARRAY_HEAP_SORT( type, a, max, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER ); \
}

#define SGLIB_ARRAY_HEAP_SORT( type, a, max, comparator, \
                               elem_exchanger )                        { \
        int _k_; \
        for( _k_=( max )/2; _k_>=0; _k_-- ) { \
            SGLIB___ARRAY_HEAP_DOWN( type, a, _k_, max, comparator, elem_exchanger ); \
        } \
        for( _k_=( max )-1; _k_>=0; _k_-- ) { \
            elem_exchanger( type, a, 0, _k_ ); \
            SGLIB___ARRAY_HEAP_DOWN( type, a, 0, _k_, comparator, elem_exchanger ); \
        } \
}

#define SGLIB___ARRAY_HEAP_DOWN( type, a, ind, max, comparator, \
                                 elem_exchanger )                      { \
        type _t_; \
        int _m_, _l_, _r_, _i_; \
        _i_ = ( ind ); \
        _m_ = _i_; \
        do { \
            _i_ = _m_;          \
            _l_ = 2*_i_+1; \
            _r_ = _l_+1; \
            if( _l_ < ( max ) ) { \
                if( comparator( ( ( a )[_m_] ), ( ( a )[_l_] ) ) < 0 ) { _m_ = _l_; }                                                             \
                if( _r_ < ( max ) ) { \
                    if( comparator( ( ( a )[_m_] ), ( ( a )[_r_] ) ) < 0 ) { _m_ = _r_; }                                                               \
                } \
            } \
            if( _m_ != _i_ ) { \
                elem_exchanger( type, a, _i_, _m_ ); \
            } \
        } while( _m_ != _i_ ); \
}

/*             QUICK - SORT   (level 0)          */

#define SGLIB_ARRAY_SINGLE_QUICK_SORT( type, a, max, \
                                       comparator )                    { \
        SGLIB_ARRAY_QUICK_SORT( type, a, max, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER ); \
}

#define SGLIB_ARRAY_QUICK_SORT( type, a, max, comparator, \
                                elem_exchanger )                       { \
        int _i_, _j_, _p_, _stacki_, _start_, _end_; \
        /* can sort up to 2^64 elements */ \
        int _startStack_[64]; \
        int _endStack_[64]; \
        type _tmp_; \
        _startStack_[0] = 0; \
        _endStack_[0] = ( max ); \
        _stacki_ = 1; \
        while( _stacki_ > 0 ) { \
            _stacki_--; \
            _start_ = _startStack_[_stacki_]; \
            _end_ = _endStack_[_stacki_]; \
            while( _end_ - _start_ > 2 ) { \
                _p_ = _start_; \
                _i_ = _start_ + 1; \
                _j_ = _end_ - 1; \
                while( _i_<_j_ ) { \
                    for(; _i_<=_j_ && comparator( ( ( a )[_i_] ), ( ( a )[_p_] ) )<=0; _i_++ ) ;                                                                                                                                                                          \
                    if( _i_ > _j_ ) { \
                        /* all remaining elements lesseq than pivot */ \
                        elem_exchanger( type, a, _j_, _p_ ); \
                        _i_ = _j_; \
                    } else { \
                        for(; _i_<=_j_ && comparator( ( ( a )[_j_] ), ( ( a )[_p_] ) )>=0; _j_-- ) ;                                                                                                                                                                                \
                        if( _i_ > _j_ ) { \
                            /* all remaining elements greater than pivot */ \
                            elem_exchanger( type, a, _j_, _p_ ); \
                            _i_ = _j_; \
                        } else if( _i_ < _j_ ) { \
                            elem_exchanger( type, a, _i_, _j_ ); \
                            if( _i_+2 < _j_ ) {_i_++; _j_--; } \
                            else if( _i_+1 < _j_ ) { _i_++; }                                         \
                        } \
                    } \
                } \
                /* O.K. i==j and pivot is on a[i] == a[j] */ \
                /* handle recursive calls without recursion */ \
                if( _i_-_start_ > 1 && _end_-_j_ > 1 ) { \
                    /* two recursive calls, use array-stack */ \
                    if( _i_-_start_ < _end_-_j_-1 ) { \
                        _startStack_[_stacki_] = _j_+1; \
                        _endStack_[_stacki_] = _end_; \
                        _stacki_++; \
                        _end_ = _i_; \
                    } else { \
                        _startStack_[_stacki_] = _start_; \
                        _endStack_[_stacki_] = _i_; \
                        _stacki_++; \
                        _start_ = _j_+1; \
                    } \
                } else { \
                    if( _i_-_start_ > 1 ) { \
                        _end_ = _i_; \
                    } else { \
                        _start_ = _j_+1; \
                    } \
                } \
            } \
            if( _end_ - _start_ == 2 ) { \
                if( comparator( ( ( a )[_start_] ), ( ( a )[_end_-1] ) ) > 0 ) { \
                    elem_exchanger( type, a, _start_, _end_-1 ); \
                } \
            } \
        } \
}

/*             BINARY SEARCH (level 0)          */

#define SGLIB_ARRAY_BINARY_SEARCH( type, a, start_index, end_index, key, comparator, found, \
                                   result_index )                      { \
        int _kk_, _cc_, _ii_, _jj_, _ff_; \
        _ii_ = ( start_index ); \
        _jj_ = ( end_index ); \
        _ff_ = 0; \
        while( _ii_ <= _jj_ && _ff_==0 ) { \
            _kk_ = ( _jj_+_ii_ )/2; \
            _cc_ = comparator( ( ( a )[_kk_] ), ( key ) ); \
            if( _cc_ == 0 ) { \
                ( result_index ) = _kk_;    \
                _ff_ = 1; \
            } else if( _cc_ < 0 ) { \
                _ii_ = _kk_+1; \
            } else { \
                _jj_ = _kk_-1; \
            } \
        } \
        if( _ff_ == 0 ) { \
            /* not found, but set its resulting place in the array */ \
            ( result_index ) = _jj_+1; \
        } \
        ( found ) = _ff_; \
}

/* -------------------------------- queue (in an array) ------------------ */
/* queue is a quadruple (a,i,j,dim) such that:                             */
/*  a is the array storing values                                          */
/*  i is the index of the first used element in the array                  */
/*  j is the index of the first free element in the array                  */
/*  dim is the size of the array a                                         */
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */

#define SGLIB_QUEUE_INIT( type, a, i, \
                          j )                                          { i = j = 0; }
#define SGLIB_QUEUE_IS_EMPTY( type, a, i, \
                              j )                                      ( ( i )==( j ) )
#define SGLIB_QUEUE_IS_FULL( type, a, i, j, \
                             dim )                                     ( ( i )==( ( j )+1 )%( dim ) )
#define SGLIB_QUEUE_FIRST_ELEMENT( type, a, i, \
                                   j )                                 ( a[i] )
#define SGLIB_QUEUE_ADD_NEXT( type, a, i, j, \
                              dim )                                    { \
        if( SGLIB_QUEUE_IS_FULL( type, a, i, j, dim ) ) { assert( 0 && "the queue is full" ); }                                                                                 \
        ( j ) = ( ( j )+1 ) % ( dim ); \
}
#define SGLIB_QUEUE_ADD( type, a, elem, i, j, \
                         dim )                                         { \
        a[j] = ( elem ); \
        SGLIB_QUEUE_ADD_NEXT( type, a, i, j, dim ); \
}
#define SGLIB_QUEUE_DELETE_FIRST( type, a, i, j, \
                                  dim )                                { \
        if( SGLIB_QUEUE_IS_EMPTY( type, a, i, j ) ) { assert( 0 && "the queue is empty" ); }                                                                              \
        ( i ) = ( ( i )+1 ) % ( dim ); \
}
#define SGLIB_QUEUE_DELETE( type, a, i, j, \
                            dim )                                      { \
        SGLIB_QUEUE_DELETE_FIRST( type, a, i, j, dim ); \
}

/* ----------------- priority queue (heap) (in an array) -------------------- */
/* heap is a triple (a,i,dim) such that:                                      */
/*  a is the array storing values                                             */
/*  i is the index of the first free element in the array                     */
/*  dim is the size of the array a                                            */
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!!    */

#define SGLIB_HEAP_INIT( type, a, \
                         i )                                           { i = 0; }
#define SGLIB_HEAP_IS_EMPTY( type, a, \
                             i )                                       ( ( i )==0 )
#define SGLIB_HEAP_IS_FULL( type, a, i, \
                            dim )                                      ( ( i )==( dim ) )
#define SGLIB_HEAP_FIRST_ELEMENT( type, a, \
                                  i )                                  ( a[0] )
#define SGLIB_HEAP_ADD_NEXT( type, a, i, dim, comparator, \
                             elem_exchanger )                          { \
        int _i_; \
        if( SGLIB_HEAP_IS_FULL( type, a, i, dim ) ) { assert( 0 && "the heap is full" ); }                                                                            \
        _i_ = ( i )++; \
        while( _i_ > 0 && comparator( a[_i_/2], a[_i_] ) < 0 ) { \
            elem_exchanger( type, a, ( _i_/2 ), _i_ ); \
            _i_ = _i_/2; \
        } \
}
#define SGLIB_HEAP_ADD( type, a, elem, i, dim, \
                        comparator )                                   { \
        if( SGLIB_HEAP_IS_FULL( type, a, i, dim ) ) { assert( 0 && "the heap is full" ); }                                                                            \
        a[i] = ( elem ); \
        SGLIB_HEAP_ADD_NEXT( type, a, i, dim, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER ); \
}
#define SGLIB_HEAP_DELETE_FIRST( type, a, i, dim, comparator, \
                                 elem_exchanger )                      { \
        if( SGLIB_HEAP_IS_EMPTY( type, a, i ) ) { assert( 0 && "the heap is empty" ); }                                                                         \
        ( i )--; \
        a[0] = a[i]; \
        SGLIB___ARRAY_HEAP_DOWN( type, a, 0, i, comparator, elem_exchanger ); \
}
#define SGLIB_HEAP_DELETE( type, a, i, dim, \
                           comparator )                                { \
        SGLIB_HEAP_DELETE_FIRST( type, a, i, dim, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER ); \
}

/* ----------------- hashed table of pointers (in an array) -------------------- */

/*
 *
 * This hashed table is storing pointers to objects (not containers).
 * In this table there is a one-to-one mapping between 'objects' stored
 * in the table and indexes where they are placed. Each index is
 * pointing to exactly one 'object' and each 'object' stored in the
 * table occurs on exactly one index.  Once an object is stored in the
 * table, it can be represented via its index.
 *
 * In case of collision while adding an object the index shifted
 * by SGLIB_HASH_TAB_SHIFT_CONSTANT (constant can be redefined)
 *
 * You can NOT delete an element from such hash table. The only
 * justification (I can see) for this data structure is an exchange
 * file format, having an index table at the beginning and then
 * refering objects via indexes.
 *
 * !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!!
 *
 */

#define SGLIB_HASH_TAB_INIT( type, table, \
                             dim )                                     { \
        int _i_; \
        for( _i_ = 0; _i_ < ( dim ); _i_++ ) ( table )[_i_] = NULL;                                                                                                                            \
}

#define SGLIB_HASH_TAB_ADD_IF_NOT_MEMBER( type, table, dim, elem, hash_function, comparator, \
                                          member )                     { \
        unsigned _pos_; \
        type     *_elem_; \
        SGLIB_HASH_TAB_FIND_MEMBER( type, table, dim, elem, _pos_, _elem_ ); \
        ( member ) = ( table )[_pos_]; \
        if( _elem_ == NULL ) { \
            if( ( table )[_pos_] != NULL ) { assert( 0 && "the hash table is full" ); }                                                                       \
            ( table )[_pos_] = ( elem ); \
        } \
}

#define SGLIB_HASH_TAB_FIND_MEMBER( type, table, dim, elem, hash_function, comparator, resultIndex, \
                                    resultMember )                     { \
        unsigned _i_; \
        int _count_; \
        type     *_e_; \
        _count = 0; \
        _i_ = hash_function( elem ); \
        _i_ %= ( dim ); \
        while( ( _e_=( table )[_i_] )!=NULL && comparator( _e_, ( elem ) )!=0 && _count_<( dim ) ) { \
                     _count_++; \
                     _i_ = ( _i_ + SGLIB_HASH_TAB_SHIFT_CONSTANT ) % ( dim ); \
                 } \
                 ( resultIndex ) = _i_; \
              if( _count_ < ( dim ) ) { ( resultMember ) = _e_; }                                             \
        else{ ( resultMember ) = NULL; }                              \
}

#define SGLIB_HASH_TAB_IS_MEMBER( type, table, dim, elem, hash_function, \
                                  resultIndex )                        { \
        unsigned _i_; \
        int _c_; \
        type     *_e_; \
        _count = 0; \
        _i_ = hash_function( elem ); \
        _i_ %= ( dim ); \
        while( ( _e_=( table )[_i_] )!=NULL && _e_!=( elem ) && _c_<( dim ) ) { \
                     _c_++; \
                     _i_ = ( _i_ + SGLIB_HASH_TAB_SHIFT_CONSTANT ) % ( dim ); \
                 } \
                 if( _e_==( elem ) ) { ( resultIndex ) = _i_; }                                        \
                 else{ ( resultIndex ) = -1; }                           \
                 }

#define SGLIB_HASH_TAB_MAP_ON_ELEMENTS( type, table, dim, iteratedIndex, iteratedVariable, \
                                        command )                      { \
    unsigned iteratedIndex; \
    type      *iteratedVariable; \
    for( iteratedIndex=0; iteratedIndex < ( dim ); iteratedIndex++ ) { \
        iteratedVariable = ( table )[iteratedIndex]; \
        if( iteratedVariable != NULL ) {command; } \
    } \
}

/* ---------------------------------------------------------------------------- */
/* ------------------------- DYNAMIC DATA STRUCTURES -------------------------- */
/* ---------------------------------------------------------------------------- */

/* ------------------------------------ lists (level 0) --------------------- */

#define SGLIB_LIST_ADD( type, list, elem, \
                        next )                                         { \
    ( elem )->next = ( list ); \
    ( list ) = ( elem ); \
}

#define SGLIB_LIST_CONCAT( type, first, second, \
                           next )                                      { \
    if( ( first )==NULL ) { \
        ( first ) = ( second ); \
    } else { \
        type *_p_; \
        for( _p_ = ( first ); _p_->next!=NULL; _p_=_p_->next ) ;                                                                                                                          \
        _p_->next = ( second ); \
    } \
}

#define SGLIB_LIST_DELETE( type, list, elem, \
                           next )                                      { \
    type **_p_; \
    for( _p_ = &( list ); *_p_!=NULL && *_p_!=( elem ); _p_= &( *_p_ )->next ) ;                                                                                                                                                        \
    assert( *_p_!=NULL && "element is not member of the container, use DELETE_IF_MEMBER instead"!=NULL ); \
    *_p_ = ( *_p_ )->next; \
}

#define SGLIB_LIST_ADD_IF_NOT_MEMBER( type, list, elem, comparator, next, \
                                      member )                         { \
    type *_p_; \
    for( _p_ = ( list ); _p_!=NULL && comparator( _p_, ( elem ) ) != 0; _p_= _p_->next ) ;                                                                                                                                                                            \
    ( member ) = _p_; \
    if( _p_ == NULL ) { \
        SGLIB_LIST_ADD( type, list, elem, next ); \
    } \
}

#define SGLIB_LIST_DELETE_IF_MEMBER( type, list, elem, comparator, next, \
                                     member )                          { \
    type **_p_; \
    for( _p_ = &( list ); *_p_!=NULL && comparator( ( *_p_ ), ( elem ) ) != 0; _p_= &( *_p_ )->next ) ;                                                                                                                                                                                                  \
    ( member ) = *_p_; \
    if( *_p_ != NULL ) { \
        *_p_ = ( *_p_ )->next; \
    } \
}

#define SGLIB_LIST_IS_MEMBER( type, list, elem, next, \
                              result )                                 { \
    type *_p_; \
    for( _p_ = ( list ); _p_!=NULL && _p_ != ( elem ); _p_= _p_->next ) ;                                                                                                                                            \
    ( result ) = ( _p_!=NULL ); \
}

#define SGLIB_LIST_FIND_MEMBER( type, list, elem, comparator, next, \
                                member )                               { \
    type *_p_; \
    for( _p_ = ( list ); _p_!=NULL && comparator( _p_, ( elem ) ) != 0; _p_= _p_->next ) ;                                                                                                                                                                            \
    ( member ) = _p_; \
}

#define SGLIB_LIST_MAP_ON_ELEMENTS( type, list, iteratedVariable, next, \
                                    command )                          { \
    type *_ne_; \
    type *iteratedVariable; \
    ( iteratedVariable ) = ( list ); \
    while( ( iteratedVariable )!=NULL ) { \
        _ne_ = ( iteratedVariable )->next; \
        {command; }; \
        ( iteratedVariable ) = _ne_; \
    } \
}

#define SGLIB_LIST_LEN( type, list, next, \
                        result )                                       { \
    type *_ce_; \
    ( result ) = 0; \
    SGLIB_LIST_MAP_ON_ELEMENTS( type, list, _ce_, next, ( result )++ ); \
}

#define SGLIB_LIST_REVERSE( type, list, \
                            next )                                     { \
    type *_list_, *_tmp_, *_res_; \
    _list_ = ( list ); \
    _res_ = NULL; \
    while( _list_!=NULL ) { \
        _tmp_ = _list_->next; _list_->next = _res_; \
        _res_ = _list_;   _list_ = _tmp_; \
    } \
    ( list ) = _res_; \
}

#define SGLIB_LIST_SORT( type, list, comparator, \
                         next )                                        { \
    /* a non-recursive merge sort on lists */ \
    type *_r_; \
    type *_a_, *_b_, *_todo_, *_t_, **_restail_; \
    int _i_, _n_, _contFlag_; \
    _r_ = ( list ); \
    _contFlag_ = 1; \
    for( _n_ = 1; _contFlag_; _n_ = _n_+_n_ ) { \
        _todo_ = _r_; _r_ = NULL; _restail_ = &_r_; _contFlag_ =0; \
        while( _todo_!=NULL ) { \
            _a_ = _todo_; \
            for( _i_ = 1, _t_ = _a_; _i_ < _n_ && _t_!=NULL; _i_++, _t_ = _t_->next ) ;                                                                                                                                                                          \
            if( _t_ ==NULL ) { \
                *_restail_ = _a_; \
                break; \
            } \
            _b_ = _t_->next; _t_->next=NULL; \
            for( _i_ =1, _t_ = _b_; _i_<_n_ && _t_!=NULL; _i_++, _t_ = _t_->next ) ;                                                                                                                                                                    \
            if( _t_ ==NULL ) { \
                _todo_ =NULL; \
            } else { \
                _todo_ = _t_->next; _t_->next=NULL; \
            } \
            /* merge */ \
            while( _a_!=NULL && _b_!=NULL ) { \
                if( comparator( _a_, _b_ ) < 0 ) { \
                    *_restail_ = _a_;  _restail_ = &( _a_->next ); _a_ = _a_->next; \
                } else { \
                    *_restail_ = _b_;  _restail_ = &( _b_->next ); _b_ = _b_->next; \
                } \
            } \
            if( _a_!=NULL ) { *_restail_ = _a_; }                                       \
            else{ *_restail_ = _b_; }                             \
            while( *_restail_!=NULL ) _restail_ = &( ( *_restail_ )->next );                                                                                                                                               \
            _contFlag_ =1; \
        } \
    } \
    ( list ) = _r_; \
}

/* --------------------------------- sorted list (level 0) --------------------- */
/*
 * All operations suppose that the list is sorted and they preserve
 * this property.
 */

#define SGLIB_SORTED_LIST_ADD( type, list, elem, comparator, \
                               next )                                  { \
    type **_e_; \
    int _cmpres_; \
    SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE( type, list, elem, comparator, next, _cmpres_, _e_ ); \
    ( elem )->next = *_e_; \
    *_e_ = ( elem ); \
}

#define SGLIB_SORTED_LIST_ADD_IF_NOT_MEMBER( type, list, elem, comparator, next, \
                                             member )                  { \
    type **_e_; \
    int _cmp_res_; \
    SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE( type, list, elem, comparator, next, _cmp_res_, _e_ ); \
    if( _cmp_res_ != 0 ) { \
        ( elem )->next = *_e_; \
        *_e_ = ( elem ); \
        ( member ) = NULL; \
    } else { \
        ( member ) = *_e_; \
    } \
}

#define SGLIB_SORTED_LIST_DELETE( type, list, elem, \
                                  next )                               { \
    SGLIB_LIST_DELETE( type, list, elem, next ); \
}

#define SGLIB_SORTED_LIST_DELETE_IF_MEMBER( type, list, elem, comparator, next, \
                                            member )                   { \
    type **_e_; \
    int _cmp_res_; \
    SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE( type, list, elem, comparator, next, _cmp_res_, _e_ ); \
    if( _cmp_res_ == 0 ) { \
        ( member ) = *_e_; \
        *_e_ = ( *_e_ )->next; \
    } else { \
        ( member ) = NULL; \
    } \
}

#define SGLIB_SORTED_LIST_FIND_MEMBER( type, list, elem, comparator, next, \
                                       member )                        { \
    type *_p_; \
    int _cmpres_ = 1; \
    for( _p_ = ( list ); _p_!=NULL && ( _cmpres_=comparator( _p_, ( elem ) ) ) < 0; _p_=_p_->next ) ;                                                                                                                                                                                                \
                                       if( _cmpres_ != 0 ) { ( member ) = NULL; }                                      \
                                       else{ ( member ) = _p_; }                       \
                                       }

#define SGLIB_SORTED_LIST_IS_MEMBER( type, list, elem, comparator, next, \
                                     result )                          { \
    type *_p_; \
    for( _p_ = ( list ); _p_!=NULL && comparator( _p_, ( elem ) ) < 0; _p_=_p_->next ) ;                                                                                                                                                                        \
    while( _p_ != NULL && _p_ != ( elem ) && comparator( _p_, ( elem ) ) == 0 ) _p_=_p_->next;                                                                                                                                                                                     \
    ( result ) = ( _p_ == ( elem ) ); \
}

#define SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE( type, list, elem, comparator, next, comparator_result, \
                                                member_ptr )           { \
    ( comparator_result ) = -1; \
    for( ( member_ptr ) = &( list ); \
        *( member_ptr )!=NULL && ( ( comparator_result )=comparator( ( *member_ptr ), ( elem ) ) ) < 0; \
                                  ( member_ptr ) = &( *( member_ptr ) )->next ) ;                                                                                                                                 \
}

#define SGLIB_SORTED_LIST_LEN( type, list, next, \
                               result )                                { \
    SGLIB_LIST_LEN( type, list, next, result ); \
}

#define SGLIB_SORTED_LIST_MAP_ON_ELEMENTS( type, list, iteratedVariable, next, \
                                           command )                   { \
    SGLIB_LIST_MAP_ON_ELEMENTS( type, list, iteratedVariable, next, command ); \
}

/* ------------------------------- double linked list (level 0) ------------------------- */
/*
 * Lists with back pointer to previous element. Those lists implements deletion
 * of an element in a constant time.
 */

#define SGLIB___DL_LIST_CREATE_SINGLETON( type, list, elem, previous, \
                                          next )                       { \
    ( list ) = ( elem ); \
    ( list )->next = ( list )->previous = NULL; \
}

#define SGLIB_DL_LIST_ADD_AFTER( type, place, elem, previous, \
                                 next )                                { \
    if( ( place ) == NULL ) { \
        SGLIB___DL_LIST_CREATE_SINGLETON( type, place, elem, previous, next ); \
    } else { \
        ( elem )->next = ( place )->next; \
        ( elem )->previous = ( place ); \
        ( place )->next = ( elem ); \
        if( ( elem )->next != NULL ) { ( elem )->next->previous = ( elem ); }                                                               \
    } \
}

#define SGLIB_DL_LIST_ADD_BEFORE( type, place, elem, previous, \
                                  next )                               { \
    if( ( place ) == NULL ) { \
        SGLIB___DL_LIST_CREATE_SINGLETON( type, place, elem, previous, next ); \
    } else { \
        ( elem )->next = ( place ); \
        ( elem )->previous = ( place )->previous; \
        ( place )->previous = ( elem ); \
        if( ( elem )->previous != NULL ) { ( elem )->previous->next = ( elem ); }                                                                   \
    } \
}

#define SGLIB_DL_LIST_ADD( type, list, elem, previous, \
                           next )                                      { \
    SGLIB_DL_LIST_ADD_BEFORE( type, list, elem, previous, next ) \
}

#define SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER( type, \
                                                   list, \
                                                   elem, \
                                                   comparator, \
                                                   previous, \
                                                   next, \
                                                   member, \
                                                   the_add_operation ) { \
    type *_dlp_; \
    for( _dlp_ = ( list ); _dlp_!=NULL && comparator( _dlp_, ( elem ) ) != 0; _dlp_= _dlp_->previous ) ;                                                                                                                                                                                                        \
    if( _dlp_ == NULL && ( list ) != NULL ) { \
        for( _dlp_ = ( list )->next; _dlp_!=NULL && comparator( _dlp_, ( elem ) ) != 0; _dlp_= _dlp_->next ) ;                                                                                                                                                                                                                  \
    } \
    ( member ) = _dlp_; \
    if( _dlp_ == NULL ) { \
        the_add_operation( type, list, elem, previous, next ); \
    } \
}

#define SGLIB_DL_LIST_ADD_BEFORE_IF_NOT_MEMBER( type, list, elem, comparator, previous, next, \
                                                member )               { \
    SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER( type, \
                                               list, \
                                               elem, \
                                               comparator, \
                                               previous, \
                                               next, \
                                               member, \
                                               SGLIB_DL_LIST_ADD_BEFORE ); \
}

#define SGLIB_DL_LIST_ADD_AFTER_IF_NOT_MEMBER( type, list, elem, comparator, previous, next, \
                                               member )                { \
    SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER( type, \
                                               list, \
                                               elem, \
                                               comparator, \
                                               previous, \
                                               next, \
                                               member, \
                                               SGLIB_DL_LIST_ADD_AFTER ); \
}

#define SGLIB_DL_LIST_ADD_IF_NOT_MEMBER( type, list, elem, comparator, previous, next, \
                                         member )                      { \
    SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER( type, list, elem, comparator, previous, next, member, SGLIB_DL_LIST_ADD ); \
}

#define SGLIB_DL_LIST_CONCAT( type, first, second, previous, \
                              next )                                   { \
    if( ( first )==NULL ) { \
        ( first ) = ( second ); \
    } else if( ( second )!=NULL ) { \
        type *_dlp_; \
        for( _dlp_ = ( first ); _dlp_->next!=NULL; _dlp_=_dlp_->next ) ;                                                                                                                                          \
        SGLIB_DL_LIST_ADD_AFTER( type, _dlp_, second, previous, next ); \
    } \
}

#define SGLIB_DL_LIST_DELETE( type, list, elem, previous, \
                              next )                                   { \
    type *_l_; \
    _l_ = ( list ); \
    if( _l_ == ( elem ) ) { \
        if( ( elem )->previous != NULL ) { _l_ = ( elem )->previous; }                                                          \
        else{ _l_ = ( elem )->next; }                             \
    } \
    if( ( elem )->next != NULL ) { ( elem )->next->previous = ( elem )->previous; }                                                                       \
    if( ( elem )->previous != NULL ) { ( elem )->previous->next = ( elem )->next; }                                                                       \
    ( list ) = _l_; \
}

#define SGLIB_DL_LIST_DELETE_IF_MEMBER( type, list, elem, comparator, previous, next, \
                                        member )                       { \
    type *_dlp_; \
    for( _dlp_ = ( list ); _dlp_!=NULL && comparator( _dlp_, ( elem ) ) != 0; _dlp_= _dlp_->previous ) ;                                                                                                                                                                                                        \
    if( _dlp_ == NULL && ( list ) != NULL ) { \
        for( _dlp_ = ( list )->next; _dlp_!=NULL && comparator( _dlp_, ( elem ) ) != 0; _dlp_= _dlp_->next ) ;                                                                                                                                                                                                                  \
    } \
    ( member ) = _dlp_; \
    if( _dlp_ != NULL ) { \
        SGLIB_DL_LIST_DELETE( type, list, _dlp_, previous, next ); \
    } \
}

#define SGLIB_DL_LIST_IS_MEMBER( type, list, elem, previous, next, \
                                 result )                              { \
    type *_dlp_; \
    SGLIB_LIST_IS_MEMBER( type, list, elem, previous, result ); \
    if( result == 0 && ( list ) != NULL ) { \
        _dlp_ = ( list )->next; \
        SGLIB_LIST_IS_MEMBER( type, _dlp_, elem, next, result ); \
    } \
}

#define SGLIB_DL_LIST_FIND_MEMBER( type, list, elem, comparator, previous, next, \
                                   member )                            { \
    type *_dlp_; \
    SGLIB_LIST_FIND_MEMBER( type, list, elem, comparator, previous, member ); \
    if( ( member ) == NULL && ( list ) != NULL ) { \
        _dlp_ = ( list )->next; \
        SGLIB_LIST_FIND_MEMBER( type, _dlp_, elem, comparator, next, member ); \
    } \
}

#define SGLIB_DL_LIST_MAP_ON_ELEMENTS( type, list, iteratedVariable, previous, next, \
                                       command )                       { \
    type *_dl_; \
    type *iteratedVariable; \
    if( ( list )!=NULL ) { \
        _dl_ = ( list )->next; \
        SGLIB_LIST_MAP_ON_ELEMENTS( type, list, iteratedVariable, previous, command ); \
        SGLIB_LIST_MAP_ON_ELEMENTS( type, _dl_, iteratedVariable, next, command ); \
    } \
}

#define SGLIB_DL_LIST_SORT( type, list, comparator, previous, \
                            next )                                     { \
    type *_dll_, *_dlp_, *_dlt_; \
    _dll_ = ( list ); \
    if( _dll_ != NULL ) { \
        for(; _dll_->previous!=NULL; _dll_=_dll_->previous ) ;                                                                                                                         \
        SGLIB_LIST_SORT( type, _dll_, comparator, next ); \
        SGLIB___DL_LIST_CREATE_FROM_LIST( type, _dll_, previous, next ); \
        ( list ) = _dll_; \
    } \
}

#define SGLIB_DL_LIST_GET_FIRST( type, list, previous, next, \
                                 result )                              { \
    type *_dll_; \
    _dll_ = ( list ); \
    if( _dll_ != NULL ) { \
        for(; _dll_->previous!=NULL; _dll_=_dll_->previous ) ;                                                                                                                         \
    } \
    ( result ) = _dll_; \
}

#define SGLIB_DL_LIST_GET_LAST( type, list, previous, next, \
                                result )                               { \
    type *_dll_; \
    _dll_ = ( list ); \
    if( _dll_ != NULL ) { \
        for(; _dll_->next!=NULL; _dll_=_dll_->next ) ;                                                                                                         \
    } \
    ( result ) = _dll_; \
}

#define SGLIB_DL_LIST_LEN( type, list, previous, next, \
                           result )                                    { \
    type *_dl_; \
    int _r1_, _r2_; \
    if( ( list )==NULL ) { \
        ( result ) = 0; \
    } else { \
        SGLIB_LIST_LEN( type, list, previous, _r1_ ); \
        _dl_ = ( list )->next; \
        SGLIB_LIST_LEN( type, _dl_, next, _r2_ ); \
        ( result ) = _r1_ + _r2_; \
    } \
}

#define SGLIB_DL_LIST_REVERSE( type, list, previous, \
                               next )                                  { \
    type *_list_, *_nlist_, *_dlp_, *_dln_; \
    _list_ = ( list ); \
    if( _list_!=NULL ) { \
        _nlist_ = _list_->next; \
        while( _list_!=NULL ) { \
            _dln_ = _list_->next; \
            _dlp_ = _list_->previous; \
            _list_->next = _dlp_; \
            _list_->previous = _dln_; \
            _list_ = _dlp_; \
        } \
        while( _nlist_!=NULL ) { \
            _dln_ = _nlist_->next; \
            _dlp_ = _nlist_->previous; \
            _nlist_->next = _dlp_; \
            _nlist_->previous = _dln_; \
            _nlist_ = _dln_; \
        } \
    } \
}

#define SGLIB___DL_LIST_CREATE_FROM_LIST( type, list, previous, \
                                          next )                       { \
    type *_dlp_, *_dlt_; \
    _dlp_ = NULL; \
    for( _dlt_ = ( list ); _dlt_!=NULL; _dlt_ = _dlt_->next ) { \
        _dlt_->previous = _dlp_; \
        _dlp_ = _dlt_; \
    } \
}

/* ------------------------------- binary tree traversal (level 0) -------------------- */

#define SGLIB___BIN_TREE_MAP_ON_ELEMENTS( type, tree, iteratedVariable, order, left, right, \
                                          command )                    { \
    /* this is non-recursive implementation of tree traversal */ \
    /* it maintains the path to the current node in the array '_path_' */ \
    /* the _path_[0] contains the root of the tree; */ \
    /* the _path_[_pathi_] contains the _current_element_ */ \
    /* the macro does not use the _current_element_ after execution of command */ \
    /* command can destroy it, it can free the element for example */ \
    type *_path_[SGLIB_MAX_TREE_DEEP]; \
    type *_right_[SGLIB_MAX_TREE_DEEP]; \
    char _pass_[SGLIB_MAX_TREE_DEEP]; \
    type *_cn_; \
    int _pathi_; \
    type *iteratedVariable; \
    _cn_ = ( tree ); \
    _pathi_ = 0; \
    while( _cn_!=NULL ) { \
        /* push down to leftmost innermost element */ \
        while( _cn_!=NULL ) { \
            _path_[_pathi_] = _cn_; \
            _right_[_pathi_] = _cn_->right; \
            _pass_[_pathi_] = 0; \
            _cn_ = _cn_->left; \
            if( order == 0 ) { \
                iteratedVariable = _path_[_pathi_]; \
                {command; } \
            } \
            _pathi_++; \
            if( _pathi_ >= SGLIB_MAX_TREE_DEEP ) { assert( 0 && "the binary_tree is too deep" ); }                                                                                      \
        } \
        do { \
            _pathi_--; \
            if( ( order==1 && _pass_[_pathi_] == 0 ) \
               || ( order == 2 && ( _pass_[_pathi_] == 1 || _right_[_pathi_]==NULL ) ) ) { \
                iteratedVariable = _path_[_pathi_]; \
                {command; } \
            } \
            _pass_[_pathi_]++; \
        } while( _pathi_>0 && _right_[_pathi_]==NULL ); \
        _cn_ = _right_[_pathi_]; \
        _right_[_pathi_] = NULL; \
        _pathi_++; \
    } \
}

#define SGLIB_BIN_TREE_MAP_ON_ELEMENTS( type, tree, _current_element_, left, right, \
                                        command )                      { \
    SGLIB___BIN_TREE_MAP_ON_ELEMENTS( type, tree, _current_element_, 1, left, right, command ); \
}

#define SGLIB_BIN_TREE_MAP_ON_ELEMENTS_PREORDER( type, tree, _current_element_, left, right, \
                                                 command )             { \
    SGLIB___BIN_TREE_MAP_ON_ELEMENTS( type, tree, _current_element_, 0, left, right, command ); \
}

#define SGLIB_BIN_TREE_MAP_ON_ELEMENTS_POSTORDER( type, tree, _current_element_, left, right, \
                                                  command )            { \
    SGLIB___BIN_TREE_MAP_ON_ELEMENTS( type, tree, _current_element_, 2, left, right, command ); \
}

#define SGLIB___BIN_TREE_FIND_MEMBER( type, tree, elem, left, right, comparator, \
                                      res )                            { \
    type *_s_; \
    int _c_; \
    _s_ = ( tree ); \
    while( _s_!=NULL ) { \
        _c_ = comparator( ( elem ), _s_ ); \
        if( _c_ < 0 ) { _s_ = _s_->left; }                                  \
        else if( _c_ > 0 ) { _s_ = _s_->right; }                                        \
        else{ break; }                \
    } \
    ( res ) = _s_; \
}

/* ---------------------------------------------------------------------------- */
/* ---------------------------------------------------------------------------- */
/* -                             LEVEL - 1  INTERFACE                         - */
/* ---------------------------------------------------------------------------- */
/* ---------------------------------------------------------------------------- */

/* ---------------------------------------------------------------------------- */
/* ------------------------------ STATIC ARRAYS ------------------------------- */
/* ---------------------------------------------------------------------------- */

/* ----------------------------- array sorting (level 1) ---------------------- */

#define SGLIB_DEFINE_ARRAY_SORTING_PROTOTYPES( type, comparator ) \
    extern void sglib_ ## type ## _array_quick_sort( type *a, int max ); \
    extern void sglib_ ## type ## _array_heap_sort( type *a, int max ); \


#define SGLIB_DEFINE_ARRAY_SORTING_FUNCTIONS( type, comparator ) \
    void sglib_ ## type ## _array_quick_sort( type *a, int max ) { \
        SGLIB_ARRAY_SINGLE_QUICK_SORT( type, a, max, comparator ); \
    } \
    void sglib_ ## type ## _array_heap_sort( type *a, int max ) { \
        SGLIB_ARRAY_SINGLE_HEAP_SORT( type, a, max, comparator ); \
    } \


/* ----------------------------- array queue (level 1) ------------------- */
/* sglib's queue is stored in a fixed sized array                          */
/* queue_type MUST be a structure containing fields:                       */
/*  afield is the array storing elem_type                                  */
/*  ifield is the index of the first element in the queue                  */
/*  jfield is the index of the first free element after the queue          */
/*  dim is the size of the array afield                                    */
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */

#define SGLIB_DEFINE_QUEUE_PROTOTYPES( queue_type, elem_type, afield, ifield, jfield, dim ) \
    extern void sglib_ ## queue_type ## _init( queue_type *q ); \
    extern int sglib_ ## queue_type ## _is_empty( queue_type *q ); \
    extern int sglib_ ## queue_type ## _is_full( queue_type *q ); \
    extern elem_type sglib_ ## queue_type ## _first_element( queue_type *q ); \
    extern elem_type *sglib_ ## queue_type ## _first_element_ptr( queue_type *q ); \
    extern void sglib_ ## queue_type ## _add_next( queue_type *q ); \
    extern void sglib_ ## queue_type ## _add( queue_type *q, elem_type elem ); \
    extern void sglib_ ## queue_type ## _delete_first( queue_type *q ); \
    extern void sglib_ ## queue_type ## _delete( queue_type *q );

#define SGLIB_DEFINE_QUEUE_FUNCTIONS( queue_type, elem_type, afield, ifield, jfield, dim ) \
    void sglib_ ## queue_type ## _init( queue_type *q ) { \
        SGLIB_QUEUE_INIT( elem_type, q->afield, q->ifield, q->jfield ); \
    } \
    int sglib_ ## queue_type ## _is_empty( queue_type *q ) { \
        return ( SGLIB_QUEUE_IS_EMPTY( elem_type, q->afield, q->ifield, q->jfield ) ); \
    } \
    int sglib_ ## queue_type ## _is_full( queue_type *q ) { \
        return ( SGLIB_QUEUE_IS_FULL( elem_type, q->afield, q->ifield, q->jfield ) ); \
    } \
    elem_type sglib_ ## queue_type ## _first_element( queue_type *q ) { \
        return ( SGLIB_QUEUE_FIRST_ELEMENT( elem_type, q->afield, q->ifield, q->jfield ) ); \
    } \
    elem_type *sglib_ ## queue_type ## _first_element_ptr( queue_type *q ) { \
        return ( &SGLIB_QUEUE_FIRST_ELEMENT( elem_type, q->afield, q->ifield, q->jfield ) ); \
    } \
    void sglib_ ## queue_type ## _add_next( queue_type *q ) { \
        SGLIB_QUEUE_ADD_NEXT( elem_type, q->afield, q->ifield, q->jfield, dim ); \
    } \
    void sglib_ ## queue_type ## _add( queue_type *q, elem_type elem ) { \
        SGLIB_QUEUE_ADD( elem_type, q->afield, elem, q->ifield, q->jfield, dim ); \
    } \
    void sglib_ ## queue_type ## _delete_first( queue_type *q ) { \
        SGLIB_QUEUE_DELETE_FIRST( elem_type, q->afield, q->ifield, q->jfield, dim ); \
    } \
    void sglib_ ## queue_type ## _delete( queue_type *q ) { \
        SGLIB_QUEUE_DELETE_FIRST( elem_type, q->afield, q->ifield, q->jfield, dim ); \
    }

/* ------------------------ array heap (level 1) ------------------------- */
/* sglib's heap is a priority queue implemented in a fixed sized array     */
/* heap_type MUST be a structure containing fields:                        */
/*  afield is the array of size dim storing elem_type                      */
/*  ifield is the index of the first free element after the queue          */
/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */

#define SGLIB_DEFINE_HEAP_PROTOTYPES( heap_type, elem_type, afield, ifield, dim, comparator, elem_exchanger ) \
    extern void sglib_ ## heap_type ## _init( heap_type *q ); \
    extern int sglib_ ## heap_type ## _is_empty( heap_type *q ); \
    extern int sglib_ ## heap_type ## _is_full( heap_type *q ); \
    extern elem_type sglib_ ## heap_type ## _first_element( heap_type *q ); \
    extern elem_type *sglib_ ## heap_type ## _first_element_ptr( heap_type *q ); \
    extern void sglib_ ## heap_type ## _add_next( heap_type *q ); \
    extern void sglib_ ## heap_type ## _add( heap_type *q, elem_type elem ); \
    extern void sglib_ ## heap_type ## _delete_first( heap_type *q ); \
    extern void sglib_ ## heap_type ## _delete( heap_type *q )

#define SGLIB_DEFINE_HEAP_FUNCTIONS( heap_type, elem_type, afield, ifield, dim, comparator, elem_exchanger ) \
    void sglib_ ## heap_type ## _init( heap_type *q ) { \
        SGLIB_HEAP_INIT( elem_type, q->afield, q->ifield ); \
    } \
    int sglib_ ## heap_type ## _is_empty( heap_type *q ) { \
        return ( SGLIB_HEAP_IS_EMPTY( elem_type, q->afield, q->ifield ) ); \
    } \
    int sglib_ ## heap_type ## _is_full( heap_type *q ) { \
        return ( SGLIB_HEAP_IS_FULL( elem_type, q->afield, q->ifield ) ); \
    } \
    elem_type sglib_ ## heap_type ## _first_element( heap_type *q ) { \
        return ( SGLIB_HEAP_FIRST_ELEMENT( elem_type, q->afield, q->ifield ) ); \
    } \
    elem_type *sglib_ ## heap_type ## _first_element_ptr( heap_type *q ) { \
        return ( &SGLIB_HEAP_FIRST_ELEMENT( elem_type, q->afield, q->ifield ) ); \
    } \
    void sglib_ ## heap_type ## _add_next( heap_type *q ) { \
        SGLIB_HEAP_ADD_NEXT( elem_type, q->afield, q->ifield, dim, comparator, elem_exchanger ); \
    } \
    void sglib_ ## heap_type ## _add( heap_type *q, elem_type elem ) { \
        SGLIB_HEAP_ADD( elem_type, q->afield, elem, q->ifield, dim, comparator, elem_exchanger ); \
    } \
    void sglib_ ## heap_type ## _delete_first( heap_type *q ) { \
        SGLIB_HEAP_DELETE_FIRST( elem_type, q->afield, q->ifield, dim, comparator, elem_exchanger ); \
    } \
    void sglib_ ## heap_type ## _delete( heap_type *q ) { \
        SGLIB_HEAP_DELETE_FIRST( elem_type, q->afield, q->ifield, dim, comparator, elem_exchanger ); \
    }

/* ------------------------ hashed table  (level 1) ------------------------- */
/*
 *
 * sglib's hash table is an array storing directly pointers to objects (not containers).
 * In this table there is a one-to-one mapping between 'objects' stored
 * in the table and indexes where they are placed. Each index is
 * pointing to exactly one 'object' and each 'object' stored in the
 * table occurs on exactly one index.  Once an object is stored in the
 * table, it can be represented via its index.
 *
 * type          - is the type of elements
 * dim           - is the size of the hash array
 * hash_function - is a hashing function mapping type* to unsigned
 * comparator    - is a comparator on elements
 *
 * !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!!
 */

#define SGLIB_DEFINE_HASHED_TABLE_PROTOTYPES( type, dim, hash_function, comparator ) \
    struct sglib_hashed_ ## type ## _iterator { \
        int currentIndex; \
        int ( *subcomparator )( type *, type * ); \
        type *equalto; \
    }; \
    extern void sglib_hashed_ ## type ## _init( type *table[dim] ); \
    extern int sglib_hashed_ ## type ## _add_if_not_member( type *table[dim], type *elem, type **member ); \
    extern int sglib_hashed_ ## type ## _is_member( type *table[dim], type *elem ); \
    extern type * sglib_hashed_ ## type ## _find_member( type *table[dim], type *elem ); \
    extern type *sglib_hashed_ ## type ## _it_init( struct sglib_hashed_ ## type ## _iterator *it, type *table[dim] ); \
    extern type *sglib_hashed_ ## type ## _it_init_on_equal( struct sglib_hashed_ ## type ## _iterator *it, \
                                                             type *table[dim], \
                                                             int ( *subcomparator )( type *, type * ), \
                                                             type *equalto ); \
    extern type *sglib_hashed_ ## type ## _it_current( struct sglib_hashed_ ## type ## _iterator *it ); \
    extern type *sglib_hashed_ ## type ## _it_next( struct sglib_hashed_ ## type ## _iterator *it );

#define SGLIB_DEFINE_HASHED_TABLE_FUNCTIONS( type, dim, hash_function, comparator ) \
    struct sglib_hashed_ ## type ## _iterator { \
        int currentIndex; \
        type **table; \
        int ( *subcomparator )( type *, type * ); \
        type *equalto; \
    }; \
    void sglib_hashed_ ## type ## _init( type *table[dim] ) { \
        SGLIB_HASH_TAB_INIT( type, table, dim ); \
    } \
    int sglib_hashed_ ## type ## _add_if_not_member( type *table[dim], type *elem, type **member ) { \
        SGLIB_HASH_TAB_ADD_IF_NOT_MEMBER( type, table, dim, elem, hash_function, comparator, *member ); \
    } \
    int sglib_hashed_ ## type ## _is_member( type *table[dim], type *elem ) { \
        int ind; \
        SGLIB_HASH_TAB_IS_MEMBER( type, table, dim, elem, hash_function, ind ); \
        return ( ind != -1 ); \
    } \
    type * sglib_hashed_ ## type ## _find_member( type *table[dim], type *elem ) { \
        type *mmb; \
        int ind; \
        SGLIB_HASH_TAB_FIND_MEMBER( type, table, dim, elem, hash_function, comparator, ind, mmb ); \
        return ( mmb ); \
    } \
    type *sglib_hashed_ ## type ## _it_init_on_equal( struct sglib_hashed_ ## type ## _iterator *it, \
                                                      type *table[dim], \
                                                      int ( *subcomparator )( type *, type * ), \
                                                      type *equalto ) { \
        int i; \
        it->table = table; \
        it->subcomparator = subcomparator; \
        it->equalto = equalto; \
        for( i=0; i<( dim ) && table[i]==NULL; i++ ) ;                                                                                                      \
        it->currentIndex = i; \
        if( i<( dim ) ) { return ( table[i] ); }                                   \
        return ( NULL ); \
    } \
    type *sglib_hashed_ ## type ## _it_init( struct sglib_hashed_ ## type ## _iterator *it, type *table[dim] ) { \
        sglib_hashed_ ## type ## _it_init_on_equal( it, table, NULL, NULL ); \
    } \
    type *sglib_hashed_ ## type ## _it_current( struct sglib_hashed_ ## type ## _iterator *it ) { \
        return ( table[it->currentIndex] ); \
    } \
    type *sglib_hashed_ ## type ## _it_next( struct sglib_hashed_ ## type ## _iterator *it ) { \
        i=it->currentIndex; \
        if( i<( dim ) ) { \
            for( i++; i<( dim ) && table[i]==NULL; i++ ) ;                                                                                                            \
        } \
        it->currentIndex = i; \
        if( i<( dim ) ) { return ( table[i] ); }                                   \
        return ( NULL ); \
    }

/* ------------------- hashed container (only for level 1)  -------------------- */
/*
 * hashed container is a table of given fixed size containing another
 * (dynamic) base container in each cell. Once an object should be
 * inserted into the hashed container, a hash function is used to
 * determine the cell where the object belongs and the object is
 * inserted into the base container stored in this cell. Usually the
 * base container is simply a list or a sorted list, but it can be a
 * red-black tree as well.
 *
 * parameters:
 * type - the type of the container stored in each cell.
 * dim  - the size of the hashed array
 * hash_function - the hashing function hashing 'type *' to unsigned.
 *
 */

#define SGLIB_DEFINE_HASHED_CONTAINER_PROTOTYPES( type, dim, hash_function ) \
    struct sglib_hashed_ ## type ## _iterator { \
        struct sglib_ ## type ## _iterator containerIt; \
        type **table; \
        int currentIndex; \
        int ( *subcomparator )( type *, type * ); \
        type *equalto; \
    }; \
    extern void sglib_hashed_ ## type ## _init( type *table[dim] ); \
    extern void sglib_hashed_ ## type ## _add( type *table[dim], type *elem ); \
    extern int sglib_hashed_ ## type ## _add_if_not_member( type *table[dim], type *elem, type **member ); \
    extern void sglib_hashed_ ## type ## _delete( type *table[dim], type *elem ); \
    extern int sglib_hashed_ ## type ## _delete_if_member( type *table[dim], type *elem, type **memb ); \
    extern int sglib_hashed_ ## type ## _is_member( type *table[dim], type *elem ); \
    extern type * sglib_hashed_ ## type ## _find_member( type *table[dim], type *elem ); \
    extern type *sglib_hashed_ ## type ## _it_init( struct sglib_hashed_ ## type ## _iterator *it, type *table[dim] ); \
    extern type *sglib_hashed_ ## type ## _it_init_on_equal( struct sglib_hashed_ ## type ## _iterator *it, \
                                                             type *table[dim], \
                                                             int ( *subcomparator )( type *, type * ), \
                                                             type *equalto ); \
    extern type *sglib_hashed_ ## type ## _it_current( struct sglib_hashed_ ## type ## _iterator *it ); \
    extern type *sglib_hashed_ ## type ## _it_next( struct sglib_hashed_ ## type ## _iterator *it );

#define SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS( type, dim, hash_function ) \
    /*extern unsigned hash_function(type *elem);*/ \
    void sglib_hashed_ ## type ## _init( type *table[dim] ) { \
        unsigned i; \
        for( i=0; i<( dim ); i++ ) table[i] = NULL;                                                                                                \
    } \
    void sglib_hashed_ ## type ## _add( type *table[dim], type *elem ) { \
        unsigned i; \
        i = ( (unsigned)hash_function( elem ) ) % ( dim ); \
        sglib_ ## type ## _add( &( table )[i], elem ); \
    } \
    int sglib_hashed_ ## type ## _add_if_not_member( type *table[dim], type *elem, type **member ) { \
        unsigned i; \
        i = ( (unsigned)hash_function( elem ) ) % ( dim ); \
        return ( sglib_ ## type ## _add_if_not_member( &( table )[i], elem, member ) ); \
    } \
    void sglib_hashed_ ## type ## _delete( type *table[dim], type *elem ) { \
        unsigned i; \
        i = ( (unsigned)hash_function( elem ) ) % ( dim ); \
        sglib_ ## type ## _delete( &( table )[i], elem ); \
    } \
    int sglib_hashed_ ## type ## _delete_if_member( type *table[dim], type *elem, type **memb ) { \
        unsigned i; \
        i = ( (unsigned)hash_function( elem ) ) % ( dim ); \
        return ( sglib_ ## type ## _delete_if_member( &( table )[i], elem, memb ) ); \
    } \
    int sglib_hashed_ ## type ## _is_member( type *table[dim], type *elem ) { \
        unsigned i; \
        i = ( (unsigned)hash_function( elem ) ) % ( dim ); \
        return ( sglib_ ## type ## _is_member( ( table )[i], elem ) ); \
    } \
    type * sglib_hashed_ ## type ## _find_member( type *table[dim], type *elem ) { \
        unsigned i; \
        i = ( (unsigned)hash_function( elem ) ) % ( dim ); \
        return ( sglib_ ## type ## _find_member( ( table )[i], elem ) ); \
    } \
    type *sglib_hashed_ ## type ## _it_init_on_equal( struct sglib_hashed_ ## type ## _iterator *it, \
                                                      type *table[dim], \
                                                      int ( *subcomparator )( type *, type * ), \
                                                      type *equalto ) { \
        type *e; \
        it->table = table; \
        it->currentIndex = 0; \
        it->subcomparator = subcomparator; \
        it->equalto = equalto; \
        e = sglib_ ## type ## _it_init_on_equal( &it->containerIt, \
                                                 table[it->currentIndex], \
                                                 it->subcomparator, \
                                                 it->equalto ); \
        if( e==NULL ) { e = sglib_hashed_ ## type ## _it_next( it ); }                                                        \
        return ( e ); \
    } \
    type *sglib_hashed_ ## type ## _it_init( struct sglib_hashed_ ## type ## _iterator *it, type *table[dim] ) { \
        return ( sglib_hashed_ ## type ## _it_init_on_equal( it, table, NULL, NULL ) ); \
    } \
    type *sglib_hashed_ ## type ## _it_current( struct sglib_hashed_ ## type ## _iterator *it ) { \
        return ( sglib_ ## type ## _it_current( &it->containerIt ) ); \
    } \
    type *sglib_hashed_ ## type ## _it_next( struct sglib_hashed_ ## type ## _iterator *it ) { \
        type *e; \
        e = sglib_ ## type ## _it_next( &it->containerIt ); \
        while( e==NULL && ( ++( it->currentIndex ) )<( dim ) ) { \
            e = sglib_ ## type ## _it_init_on_equal( &it->containerIt, \
                                                     it->table[it->currentIndex], \
                                                     it->subcomparator, \
                                                     it->equalto ); \
        } \
        return ( e ); \
    }

/* ---------------------------------------------------------------------------- */
/* ------------------------- DYNAMIC DATA STRUCTURES -------------------------- */
/* ---------------------------------------------------------------------------- */

/* ------------------------------------ list (level 1) -------------------------------- */

#define SGLIB_DEFINE_LIST_PROTOTYPES( type, comparator, next ) \
    struct sglib_ ## type ## _iterator { \
        type *currentelem; \
        type *nextelem; \
        int ( *subcomparator )( type *, type * ); \
        type *equalto; \
    }; \
    extern void sglib_ ## type ## _add( type **list, type *elem ); \
    extern int sglib_ ## type ## _add_if_not_member( type **list, type *elem, type **member ); \
    extern void sglib_ ## type ## _concat( type **first, type *second ); \
    extern void sglib_ ## type ## _delete( type **list, type *elem ); \
    extern int sglib_ ## type ## _delete_if_member( type **list, type *elem, type **member ); \
    extern int sglib_ ## type ## _is_member( type *list, type *elem ); \
    extern type *sglib_ ## type ## _find_member( type *list, type *elem ); \
    extern void sglib_ ## type ## _sort( type **list ); \
    extern int sglib_ ## type ## _len( type *list ); \
    extern void sglib_ ## type ## _reverse( type **list ); \
    extern type *sglib_ ## type ## _it_init( struct sglib_ ## type ## _iterator *it, type *list ); \
    extern type *sglib_ ## type ## _it_init_on_equal( struct sglib_ ## type ## _iterator *it, type *list, \
                                                      int ( *subcomparator )( type *, type * ), type *equalto ); \
    extern type *sglib_ ## type ## _it_current( struct sglib_ ## type ## _iterator *it ); \
    extern type *sglib_ ## type ## _it_next( struct sglib_ ## type ## _iterator *it );

#define SGLIB_DEFINE_LIST_FUNCTIONS( type, comparator, next ) \
    int sglib_ ## type ## _is_member( type *list, type *elem ) { \
        int result; \
        SGLIB_LIST_IS_MEMBER( type, list, elem, next, result ); \
        return ( result ); \
    } \
    type *sglib_ ## type ## _find_member( type *list, type *elem ) { \
        type *result; \
        SGLIB_LIST_FIND_MEMBER( type, list, elem, comparator, next, result ); \
        return ( result ); \
    } \
    int sglib_ ## type ## _add_if_not_member( type **list, type *elem, type **member ) { \
        SGLIB_LIST_ADD_IF_NOT_MEMBER( type, *list, elem, comparator, next, *member ); \
        return ( *member==NULL ); \
    } \
    void sglib_ ## type ## _add( type **list, type *elem ) { \
        SGLIB_LIST_ADD( type, *list, elem, next ); \
    } \
    void sglib_ ## type ## _concat( type **first, type *second ) { \
        SGLIB_LIST_CONCAT( type, *first, second, next ); \
    } \
    void sglib_ ## type ## _delete( type **list, type *elem ) { \
        SGLIB_LIST_DELETE( type, *list, elem, next ); \
    } \
    int sglib_ ## type ## _delete_if_member( type **list, type *elem, type **member ) { \
        SGLIB_LIST_DELETE_IF_MEMBER( type, *list, elem, comparator, next, *member ); \
        return ( *member!=NULL ); \
    } \
    void sglib_ ## type ## _sort( type **list ) { \
        SGLIB_LIST_SORT( type, *list, comparator, next ); \
    } \
    int sglib_ ## type ## _len( type *list ) { \
        int res; \
        SGLIB_LIST_LEN( type, list, next, res ); \
        return ( res ); \
    } \
    void sglib_ ## type ## _reverse( type **list ) { \
        SGLIB_LIST_REVERSE( type, *list, next ); \
    } \
 \
    type *sglib_ ## type ## _it_init_on_equal( struct sglib_ ## type ## _iterator *it, type *list, \
                                               int ( *subcomparator )( type *, type * ), type *equalto ) { \
        it->subcomparator = subcomparator; \
        it->equalto = equalto; \
        it->nextelem = list; \
        return ( sglib_ ## type ## _it_next( it ) ); \
    } \
    type *sglib_ ## type ## _it_init( struct sglib_ ## type ## _iterator *it, type *list ) { \
        return ( sglib_ ## type ## _it_init_on_equal( it, list, NULL, NULL ) ); \
    } \
    type *sglib_ ## type ## _it_current( struct sglib_ ## type ## _iterator *it ) { \
        return ( it->currentelem ); \
    } \
    type *sglib_ ## type ## _it_next( struct sglib_ ## type ## _iterator *it ) { \
        type *ce, *eq; \
        int ( *scp )( type *, type * ); \
        ce = it->nextelem; \
        it->nextelem = NULL; \
        if( it->subcomparator != NULL ) { \
            eq = it->equalto; \
            scp = it->subcomparator; \
            while( ce!=NULL && scp( ce, eq )!=0 ) ce = ce->next;                                                                                                                        \
        } \
        it->currentelem = ce; \
        if( ce != NULL ) { it->nextelem = ce->next; }                                            \
        return ( ce ); \
    }

/* ----------------------------- sorted list (level 1) ----------------------------------- */

#define SGLIB_DEFINE_SORTED_LIST_PROTOTYPES( type, comparator, next ) \
    struct sglib_ ## type ## _iterator { \
        type *currentelem; \
        type *nextelem; \
        int ( *subcomparator )( type *, type * ); \
        type *equalto; \
    }; \
    extern void sglib_ ## type ## _add( type **list, type *elem ); \
    extern int sglib_ ## type ## _add_if_not_member( type **list, type *elem, type **member ); \
    extern void sglib_ ## type ## _delete( type **list, type *elem ); \
    extern int sglib_ ## type ## _delete_if_member( type **list, type *elem, type **member ); \
    extern int sglib_ ## type ## _is_member( type *list, type *elem ); \
    extern type *sglib_ ## type ## _find_member( type *list, type *elem ); \
    extern int sglib_ ## type ## _len( type *list ); \
    extern void sglib_ ## type ## _sort( type **list ); \
    extern type *sglib_ ## type ## _it_init( struct sglib_ ## type ## _iterator *it, type *list ); \
    extern type *sglib_ ## type ## _it_init_on_equal( struct sglib_ ## type ## _iterator *it, type *list, \
                                                      int ( *subcomparator )( type *, type * ), type *equalto ); \
    extern type *sglib_ ## type ## _it_current( struct sglib_ ## type ## _iterator *it ); \
    extern type *sglib_ ## type ## _it_next( struct sglib_ ## type ## _iterator *it );

#define SGLIB_DEFINE_SORTED_LIST_FUNCTIONS( type, comparator, next ) \
    int sglib_ ## type ## _is_member( type *list, type *elem ) { \
        int result; \
        SGLIB_SORTED_LIST_IS_MEMBER( type, list, elem, comparator, next, result ); \
        return ( result ); \
    } \
    type *sglib_ ## type ## _find_member( type *list, type *elem ) { \
        type *result; \
        SGLIB_SORTED_LIST_FIND_MEMBER( type, list, elem, comparator, next, result ); \
        return ( result ); \
    } \
    int sglib_ ## type ## _add_if_not_member( type **list, type *elem, type **member ) { \
        SGLIB_SORTED_LIST_ADD_IF_NOT_MEMBER( type, *list, elem, comparator, next, *member ); \
        return ( *member==NULL ); \
    } \
    void sglib_ ## type ## _add( type **list, type *elem ) { \
        SGLIB_SORTED_LIST_ADD( type, *list, elem, comparator, next ); \
    } \
    void sglib_ ## type ## _delete( type **list, type *elem ) { \
        SGLIB_SORTED_LIST_DELETE( type, *list, elem, next ); \
    } \
    int sglib_ ## type ## _delete_if_member( type **list, type *elem, type **member ) { \
        SGLIB_SORTED_LIST_DELETE_IF_MEMBER( type, *list, elem, comparator, next, *member ); \
        return ( *member!=NULL ); \
    } \
    int sglib_ ## type ## _len( type *list ) { \
        int res; \
        SGLIB_SORTED_LIST_LEN( type, list, next, res ); \
        return ( res ); \
    } \
    void sglib_ ## type ## _sort( type **list ) { \
        SGLIB_LIST_SORT( type, *list, comparator, next ); \
    } \
 \
    type *sglib_ ## type ## _it_init_on_equal( struct sglib_ ## type ## _iterator *it, type *list, \
                                               int ( *subcomparator )( type *, type * ), type *equalto ) { \
        it->subcomparator = subcomparator; \
        it->equalto = equalto; \
        it->nextelem = list; \
        return ( sglib_ ## type ## _it_next( it ) ); \
    } \
    type *sglib_ ## type ## _it_init( struct sglib_ ## type ## _iterator *it, type *list ) { \
        return ( sglib_ ## type ## _it_init_on_equal( it, list, NULL, NULL ) ); \
    } \
    type *sglib_ ## type ## _it_current( struct sglib_ ## type ## _iterator *it ) { \
        return ( it->currentelem ); \
    } \
    type *sglib_ ## type ## _it_next( struct sglib_ ## type ## _iterator *it ) { \
        type *ce, *eq; \
        int ( *scp )( type *, type * ); \
        int c; \
        ce = it->nextelem; \
        it->nextelem = NULL; \
        if( it->subcomparator != NULL ) { \
            eq = it->equalto; \
            scp = it->subcomparator; \
            while( ce!=NULL && ( c=scp( ce, eq ) ) < 0 ) ce = ce->next;                                                                                                                                    \
                                if( ce != NULL && c > 0 ) { ce = NULL; }                                         \
                                } \
                                it->currentelem = ce; \
                                if( ce != NULL ) { it->nextelem = ce->next; }                                            \
                                return ( ce ); \
                                }

/* ----------------------------- double linked list (level 1) ------------------------------ */

#define SGLIB_DEFINE_DL_LIST_PROTOTYPES( type, comparator, previous, next ) \
    struct sglib_ ## type ## _iterator { \
        type *currentelem; \
        type *prevelem; \
        type *nextelem; \
        int ( *subcomparator )( type *, type * ); \
        type *equalto; \
    }; \
    extern void sglib_ ## type ## _add( type **list, type *elem ); \
    extern void sglib_ ## type ## _add_before( type **list, type *elem ); \
    extern void sglib_ ## type ## _add_after( type **list, type *elem ); \
    extern int sglib_ ## type ## _add_if_not_member( type **list, type *elem, type **member ); \
    extern int sglib_ ## type ## _add_before_if_not_member( type **list, type *elem, type **member ); \
    extern int sglib_ ## type ## _add_after_if_not_member( type **list, type *elem, type **member ); \
    extern void sglib_ ## type ## _concat( type **first, type *second ); \
    extern void sglib_ ## type ## _delete( type **list, type *elem ); \
    extern int sglib_ ## type ## _delete_if_member( type **list, type *elem, type **member ); \
    extern int sglib_ ## type ## _is_member( type *list, type *elem ); \
    extern type *sglib_ ## type ## _find_member( type *list, type *elem ); \
    extern type *sglib_ ## type ## _get_first( type *list ); \
    extern type *sglib_ ## type ## _get_last( type *list ); \
    extern void sglib_ ## type ## _sort( type **list ); \
    extern int sglib_ ## type ## _len( type *list ); \
    extern void sglib_ ## type ## _reverse( type **list ); \
    extern type *sglib_ ## type ## _it_init( struct sglib_ ## type ## _iterator *it, type *list ); \
    extern type *sglib_ ## type ## _it_init_on_equal( struct sglib_ ## type ## _iterator *it, type *list, \
                                                      int ( *subcomparator )( type *, type * ), type *equalto ); \
    extern type *sglib_ ## type ## _it_current( struct sglib_ ## type ## _iterator *it ); \
    extern type *sglib_ ## type ## _it_next( struct sglib_ ## type ## _iterator *it );

#define SGLIB_DEFINE_DL_LIST_FUNCTIONS( type, comparator, previous, next ) \
    void sglib_ ## type ## _add( type **list, type *elem ) { \
        SGLIB_DL_LIST_ADD( type, *list, elem, previous, next ); \
    } \
    void sglib_ ## type ## _add_after( type **list, type *elem ) { \
        SGLIB_DL_LIST_ADD_AFTER( type, *list, elem, previous, next ); \
    } \
    void sglib_ ## type ## _add_before( type **list, type *elem ) { \
        SGLIB_DL_LIST_ADD_BEFORE( type, *list, elem, previous, next ); \
    } \
    int sglib_ ## type ## _add_if_not_member( type **list, type *elem, type **member ) { \
        SGLIB_DL_LIST_ADD_IF_NOT_MEMBER( type, *list, elem, comparator, previous, next, *member ); \
        return ( *member==NULL ); \
    } \
    int sglib_ ## type ## _add_after_if_not_member( type **list, type *elem, type **member ) { \
        SGLIB_DL_LIST_ADD_AFTER_IF_NOT_MEMBER( type, *list, elem, comparator, previous, next, *member ); \
        return ( *member==NULL ); \
    } \
    int sglib_ ## type ## _add_before_if_not_member( type **list, type *elem, type **member ) { \
        SGLIB_DL_LIST_ADD_BEFORE_IF_NOT_MEMBER( type, *list, elem, comparator, previous, next, *member ); \
        return ( *member==NULL ); \
    } \
    void sglib_ ## type ## _concat( type **first, type *second ) { \
        SGLIB_DL_LIST_CONCAT( type, *first, second, previous, next ); \
    } \
    void sglib_ ## type ## _delete( type **list, type *elem ) { \
        SGLIB_DL_LIST_DELETE( type, *list, elem, previous, next ); \
    } \
    int sglib_ ## type ## _delete_if_member( type **list, type *elem, type **member ) { \
        SGLIB_DL_LIST_DELETE_IF_MEMBER( type, *list, elem, comparator, previous, next, *member ); \
        return ( *member!=NULL ); \
    } \
    int sglib_ ## type ## _is_member( type *list, type *elem ) { \
        int result; \
        SGLIB_DL_LIST_IS_MEMBER( type, list, elem, previous, next, result ); \
        return ( result ); \
    } \
    type *sglib_ ## type ## _find_member( type *list, type *elem ) { \
        type *result; \
        SGLIB_DL_LIST_FIND_MEMBER( type, list, elem, comparator, previous, next, result ); \
        return ( result ); \
    } \
    type *sglib_ ## type ## _get_first( type *list ) { \
        type *result; \
        SGLIB_DL_LIST_GET_FIRST( type, list, previous, next, result ); \
        return ( result ); \
    } \
    type *sglib_ ## type ## _get_last( type *list ) { \
        type *result; \
        SGLIB_DL_LIST_GET_LAST( type, list, previous, next, result ); \
        return ( result ); \
    } \
    void sglib_ ## type ## _sort( type **list ) { \
        SGLIB_DL_LIST_SORT( type, *list, comparator, previous, next ); \
    } \
    int sglib_ ## type ## _len( type *list ) { \
        int res; \
        SGLIB_DL_LIST_LEN( type, list, previous, next, res ); \
        return ( res ); \
    } \
    void sglib_ ## type ## _reverse( type **list ) { \
        SGLIB_DL_LIST_REVERSE( type, *list, previous, next ); \
    } \
 \
    type *sglib_ ## type ## _it_init_on_equal( struct sglib_ ## type ## _iterator *it, type *list, \
                                               int ( *subcomparator )( type *, type * ), type *equalto ) { \
        it->subcomparator = subcomparator; \
        it->equalto = equalto; \
        it->prevelem = list; \
        it->nextelem = list; \
        if( list != NULL ) { it->nextelem = list->next; }                                                \
        return ( sglib_ ## type ## _it_next( it ) ); \
    } \
    type *sglib_ ## type ## _it_init( struct sglib_ ## type ## _iterator *it, type *list ) { \
        return ( sglib_ ## type ## _it_init_on_equal( it, list, NULL, NULL ) ); \
    } \
    type *sglib_ ## type ## _it_current( struct sglib_ ## type ## _iterator *it ) { \
        return ( it->currentelem ); \
    } \
    type *sglib_ ## type ## _it_next( struct sglib_ ## type ## _iterator *it ) { \
        type *ce, *eq; \
        int ( *scp )( type *, type * ); \
        ce = it->prevelem; \
        it->prevelem = NULL; \
        if( it->subcomparator != NULL ) { \
            eq = it->equalto; \
            scp = it->subcomparator; \
            while( ce!=NULL && scp( eq, ce )!=0 ) ce = ce->previous;                                                                                                                                \
        } \
        if( ce != NULL ) { \
            it->prevelem = ce->previous; \
        } else { \
            ce = it->nextelem; \
            it->nextelem = NULL; \
            if( it->subcomparator != NULL ) { \
                eq = it->equalto; \
                scp = it->subcomparator; \
                while( ce!=NULL && scp( ce, eq )!=0 ) ce = ce->next;                                                                                                                              \
            } \
            if( ce != NULL ) { it->nextelem = ce->next; }                                              \
        } \
        it->currentelem = ce; \
        return ( ce ); \
    }

/* --------------------------------- red-black trees (level 1) -------------------------------- */

/*
 *
 * This  implementation requires  pointers  to left  and  right sons  (no
 * parent  pointer  is needed)  and  one  bit  of additional  information
 * storing the color of  the node. The implementation follows discrepancy
 * fixing rules from:
 * http://www.cis.ohio-state.edu/~gurari/course/cis680/cis680Ch11.html
 *
 */

#define SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY( type, tree, leftt, rightt, bits, RED, BLACK )     { \
    type *t, *tl, *a, *b, *c, *ar, *bl, *br, *cl, *cr; \
    t = *tree; \
    tl = t->leftt; \
    if( t->rightt!=NULL && SGLIB___GET_VALUE( t->rightt->bits )==RED ) { \
        if( SGLIB___GET_VALUE( tl->bits )==RED ) { \
            if( ( tl->leftt!=NULL && SGLIB___GET_VALUE( tl->leftt->bits )==RED ) \
               || ( tl->rightt!=NULL && SGLIB___GET_VALUE( tl->rightt->bits )==RED ) ) { \
                SGLIB___SET_VALUE( t->leftt->bits, BLACK ); \
                SGLIB___SET_VALUE( t->rightt->bits, BLACK ); \
                SGLIB___SET_VALUE( t->bits, RED ); \
            } \
        } \
    } else { \
        if( SGLIB___GET_VALUE( tl->bits )==RED ) { \
            if( tl->leftt!=NULL && SGLIB___GET_VALUE( tl->leftt->bits )==RED ) { \
                a = t; b = tl; c = tl->leftt; \
                br = b->rightt; \
                a->leftt = br; \
                b->leftt = c; b->rightt = a; \
                SGLIB___SET_VALUE( a->bits, RED ); \
                SGLIB___SET_VALUE( b->bits, BLACK ); \
                *tree = b; \
            } else if( tl->rightt!=NULL && SGLIB___GET_VALUE( tl->rightt->bits )==RED ) { \
                a = t; b = tl; ar=a->rightt; \
                bl=b->leftt; c=b->rightt; \
                cl=c->leftt; cr=c->rightt; \
                b->rightt = cl; \
                a->leftt = cr; \
                c->leftt = b; \
                c->rightt = a; \
                SGLIB___SET_VALUE( c->bits, BLACK ); \
                SGLIB___SET_VALUE( a->bits, RED ); \
                *tree = c; \
            } \
        } \
    } \
}

#define SGLIB___RBTREE_FIX_DELETION_DISCREPANCY( type, tree, leftt, rightt, bits, RED, BLACK, res ) { \
    type  *t, *a, *b, *c, *d, *ar, *bl, *br, *cl, *cr, *dl, *dr; \
    t = a = *tree; \
    assert( t!=NULL ); \
    ar = a->rightt; \
    b = t->leftt; \
    if( b==NULL ) { \
        assert( SGLIB___GET_VALUE( t->bits )==RED ); \
        SGLIB___SET_VALUE( t->bits, BLACK ); \
        res = 0; \
    } else { \
        bl = b->leftt; \
        br = b->rightt; \
        if( SGLIB___GET_VALUE( b->bits )==RED ) { \
            if( br==NULL ) { \
                *tree = b; \
                SGLIB___SET_VALUE( b->bits, BLACK ); \
                b->rightt = a; \
                a->leftt = br; \
                res = 0; \
            } else { \
                c = br; \
                assert( c!=NULL && SGLIB___GET_VALUE( c->bits )==BLACK ); \
                cl = c->leftt; \
                cr = c->rightt; \
                if( ( cl==NULL|| \
                      SGLIB___GET_VALUE( cl->bits )==BLACK ) && ( cr==NULL||SGLIB___GET_VALUE( cr->bits )==BLACK ) ) { \
                    *tree = b; \
                    b->rightt = a; \
                    SGLIB___SET_VALUE( b->bits, BLACK ); \
                    a->leftt = c; \
                    SGLIB___SET_VALUE( c->bits, RED ); \
                    res = 0; \
                } else if( cl!=NULL && SGLIB___GET_VALUE( cl->bits )==RED ) { \
                    if( cr!=NULL && SGLIB___GET_VALUE( cr->bits )==RED ) { \
                        d = cr; \
                        dl = d->leftt; \
                        dr = d->rightt; \
                        *tree = d; \
                        SGLIB___SET_VALUE( d->bits, BLACK ); \
                        d->leftt = b; \
                        c->rightt = dl; \
                        d->rightt = a; \
                        a->leftt = dr; \
                        res = 0; \
                    } else { \
                        *tree = c; \
                        c->leftt = b; \
                        c->rightt = a; \
                        b->leftt = bl; \
                        b->rightt = cl; \
                        a->leftt = cr; \
                        SGLIB___SET_VALUE( cl->bits, BLACK ); \
                        res = 0; \
                    } \
                } else if( cr!=NULL && SGLIB___GET_VALUE( cr->bits )==RED ) { \
                    assert( cl==NULL || SGLIB___GET_VALUE( cl->bits )==BLACK ); \
                    d = cr; \
                    dl = d->leftt; \
                    dr = d->rightt; \
                    *tree = d; \
                    SGLIB___SET_VALUE( d->bits, BLACK ); \
                    d->leftt = b; \
                    c->rightt = dl; \
                    d->rightt = a; \
                    a->leftt = dr; \
                    res = 0; \
                } else { \
                    assert( 0 ); \
                    res = 0; \
                } \
            } \
        } else { \
            if( ( bl==NULL || \
                  SGLIB___GET_VALUE( bl->bits )==BLACK ) && ( br==NULL || SGLIB___GET_VALUE( br->bits )==BLACK ) ) { \
                res = ( SGLIB___GET_VALUE( a->bits )==BLACK ); \
                SGLIB___SET_VALUE( a->bits, BLACK ); \
                SGLIB___SET_VALUE( b->bits, RED ); \
            } else if( bl!=NULL && SGLIB___GET_VALUE( bl->bits )==RED ) { \
                if( br==NULL || SGLIB___GET_VALUE( br->bits )==BLACK ) { \
                    *tree = b; \
                    SGLIB___SET_VALUE( b->bits, SGLIB___GET_VALUE( a->bits ) ); \
                    SGLIB___SET_VALUE( a->bits, BLACK ); \
                    b->rightt = a; \
                    a->leftt = br; \
                    SGLIB___SET_VALUE( bl->bits, BLACK ); \
                    res = 0; \
                } else { \
                    assert( bl!=NULL ); \
                    assert( br!=NULL ); \
                    assert( SGLIB___GET_VALUE( bl->bits )==RED ); \
                    assert( SGLIB___GET_VALUE( br->bits )==RED ); \
                    c = br; \
                    cl = c->leftt; \
                    cr = c->rightt; \
                    *tree = c; \
                    SGLIB___SET_VALUE( c->bits, SGLIB___GET_VALUE( a->bits ) ); \
                    SGLIB___SET_VALUE( a->bits, BLACK ); \
                    c->leftt = b; \
                    c->rightt = a; \
                    b->rightt = cl; \
                    a->leftt = cr; \
                    res = 0; \
                } \
            } else { \
                assert( br!=NULL && SGLIB___GET_VALUE( br->bits )==RED ); \
                c = br; \
                cl = c->leftt; \
                cr = c->rightt; \
                *tree = c; \
                SGLIB___SET_VALUE( c->bits, SGLIB___GET_VALUE( a->bits ) ); \
                SGLIB___SET_VALUE( a->bits, BLACK ); \
                c->leftt = b; \
                c->rightt = a; \
                b->rightt = cl; \
                a->leftt = cr; \
                res = 0; \
            } \
        } \
    } \
}

#define SGLIB_DEFINE_RBTREE_FUNCTIONS_GENERAL( type, left, right, bits, comparator, RED, BLACK ) \
    static void sglib___ ## type ## _fix_left_insertion_discrepancy( type **tree ) { \
        SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY( type, tree, left, right, bits, RED, BLACK ); \
    } \
\
    static void sglib___ ## type ## _fix_right_insertion_discrepancy( type **tree ) { \
        SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY( type, tree, right, left, bits, RED, BLACK ); \
    } \
\
    static int sglib___ ## type ## _fix_left_deletion_discrepancy( type **tree ) { \
        int res; \
        SGLIB___RBTREE_FIX_DELETION_DISCREPANCY( type, tree, right, left, bits, RED, BLACK, res ); \
        return ( res ); \
    } \
\
    static int sglib___ ## type ## _fix_right_deletion_discrepancy( type **tree ) { \
        int res; \
        SGLIB___RBTREE_FIX_DELETION_DISCREPANCY( type, tree, left, right, bits, RED, BLACK, res ); \
        return ( res ); \
    } \
\
    static void sglib___ ## type ## _add_recursive( type **tree, type *elem ) { \
        int cmp; \
        type *t; \
        t = *tree; \
        if( t == NULL ) { \
            SGLIB___SET_VALUE( elem->bits, RED ); \
            *tree =elem; \
        } else { \
            cmp = comparator( elem, t ); \
            if( cmp < 0 || ( cmp==0 && elem<t ) ) { \
                sglib___ ## type ## _add_recursive( &t->left, elem ); \
                if( SGLIB___GET_VALUE( t->bits )==BLACK ) { sglib___ ## type ## _fix_left_insertion_discrepancy( tree ); }                                                                                                    \
            } else { \
                sglib___ ## type ## _add_recursive( &t->right, elem ); \
                if( SGLIB___GET_VALUE( t->bits )==BLACK ) { sglib___ ## type ## _fix_right_insertion_discrepancy( tree ); }                                                                                                     \
            } \
        } \
    } \
\
    static int sglib___ ## type ## _delete_rightmost_leaf( type **tree, type **theLeaf ) { \
        type  *t; \
        int res, deepDecreased; \
        t = *tree; \
        res = 0; \
        assert( t!=NULL ); \
        if( t->right == NULL ) { \
            *theLeaf = t; \
            if( t->left!=NULL ) { \
                if( SGLIB___GET_VALUE( t->bits )==BLACK && SGLIB___GET_VALUE( t->left->bits )==BLACK ) { res = 1; }                                                                                                 \
                SGLIB___SET_VALUE( t->left->bits, BLACK ); \
                *tree = t->left; \
            } else { \
                *tree = NULL; \
                res = ( SGLIB___GET_VALUE( t->bits )==BLACK ); \
            } \
        } else { \
            deepDecreased = sglib___ ## type ## _delete_rightmost_leaf( &t->right, theLeaf ); \
            if( deepDecreased ) { res = sglib___ ## type ## _fix_right_deletion_discrepancy( tree ); }                                                                                    \
        } \
        return ( res ); \
    } \
\
    int sglib___ ## type ## _delete_recursive( type **tree, type *elem ) { \
        type  *t, *theLeaf; \
        int cmp, res, deepDecreased; \
        t = *tree; \
        res = 0; \
        if( t==NULL ) { \
            assert( 0 && "The element to delete not found in the tree,  use 'delete_if_member'"!=NULL ); \
        } else { \
            cmp = comparator( elem, t ); \
            if( cmp < 0 || ( cmp==0 && elem<t ) ) { \
                deepDecreased = sglib___ ## type ## _delete_recursive( &t->left, elem ); \
                if( deepDecreased ) { \
                    res = sglib___ ## type ## _fix_left_deletion_discrepancy( tree ); \
                } \
            } else if( cmp > 0  || ( cmp==0 && elem>t ) ) { \
                deepDecreased = sglib___ ## type ## _delete_recursive( &t->right, elem ); \
                if( deepDecreased ) { \
                    res = sglib___ ## type ## _fix_right_deletion_discrepancy( tree ); \
                } \
            } else { \
                assert( elem==t && "Deleting an element which is non member of the tree, use 'delete_if_member'"!=NULL ); \
                if( t->left == NULL ) { \
                    if( t->right == NULL ) { \
                        /* a leaf, delete, it; */ \
                        *tree = NULL; \
                        res = ( SGLIB___GET_VALUE( t->bits )==BLACK ); \
                    } else { \
                        if( SGLIB___GET_VALUE( t->bits )==0 && SGLIB___GET_VALUE( t->right->bits )==0 ) { res = 1; }                                                                                              \
                        SGLIB___SET_VALUE( t->right->bits, BLACK ); \
                        *tree = t->right; \
                    } \
                } else { \
                    /* propagate deletion until righmost leaf of left subtree */ \
                    deepDecreased = sglib___ ## type ## _delete_rightmost_leaf( &t->left, &theLeaf ); \
                    theLeaf->left = t->left; \
                    theLeaf->right = t->right; \
                    SGLIB___SET_VALUE( theLeaf->bits, SGLIB___GET_VALUE( t->bits ) ); \
                    *tree = theLeaf; \
                    if( deepDecreased ) { res = sglib___ ## type ## _fix_left_deletion_discrepancy( tree ); }                                                                                       \
                } \
            } \
        } \
        return ( res ); \
    } \
\
    void sglib_ ## type ## _add( type **tree, type *elem ) { \
        elem->left = elem->right = NULL; \
        sglib___ ## type ## _add_recursive( tree, elem ); \
        SGLIB___SET_VALUE( ( *tree )->bits, BLACK ); \
    } \
\
    void sglib_ ## type ## _delete( type **tree, type *elem ) { \
        sglib___ ## type ## _delete_recursive( tree, elem ); \
        if( *tree!=NULL ) { SGLIB___SET_VALUE( ( *tree )->bits, BLACK ); }                                                           \
    } \
\
    type *sglib_ ## type ## _find_member( type *t, type *elem ) { \
        type *res; \
        SGLIB___BIN_TREE_FIND_MEMBER( type, t, elem, left, right, comparator, res ); \
        return ( res ); \
    } \
\
    int sglib_ ## type ## _is_member( type *t, type *elem ) { \
        int cmp; \
        while( t!=NULL ) { \
            cmp = comparator( elem, t ); \
            if( cmp < 0 || ( cmp==0 && elem<t ) ) { \
                t = t->left; \
            } else if( cmp > 0 || ( cmp==0 && elem>t ) ) { \
                t = t->right; \
            } else { \
                assert( t == elem ); \
                return ( 1 ); \
            } \
        } \
        return ( 0 ); \
    } \
\
    int sglib_ ## type ## _delete_if_member( type **tree, type *elem, type **memb ) { \
        if( ( *memb=sglib_ ## type ## _find_member( *tree, elem ) )!=NULL ) { \
                 sglib_ ## type ## _delete( tree, *memb ); \
                 return ( 1 ); \
             } else { \
                 return ( 0 ); \
             } \
             } \
             int sglib_ ## type ## _add_if_not_member( type **tree, type *elem, type **memb ) { \
                 if( ( *memb=sglib_ ## type ## _find_member( *tree, elem ) )==NULL ) { \
                          sglib_ ## type ## _add( tree, elem ); \
                          return ( 1 ); \
                      } else { \
                          return ( 0 ); \
                      } \
                      } \
                      int sglib_ ## type ## _len( type *t ) { \
                          int n; \
                          type  *e; \
                          n = 0; \
                          SGLIB_BIN_TREE_MAP_ON_ELEMENTS( type, t, e, left, right, n++ ); \
                          return ( n ); \
                      } \
\
                      void sglib__ ## type ## _it_compute_current_elem( struct sglib_ ## type ## _iterator *it ) { \
                          int i, j, cmp; \
                          type  *s, *eqt; \
                          int ( *subcomparator )( type *, type * ); \
                          eqt = it->equalto; \
                          subcomparator = it->subcomparator; \
                          it->currentelem = NULL; \
                          while( it->pathi > 0 && it->currentelem==NULL ) { \
                              i = it->pathi-1; \
                              if( i >= 0 ) { \
                                  if( it->pass[i] >= 2 ) { \
                                      /* goto up */ \
                                      it->pathi--; \
                                  } else { \
                                      if( it->pass[i] == 0 ) { \
                                          /* goto left */ \
                                          s = it->path[i]->left; \
                                      } else { \
                                          /* goto right */ \
                                          s = it->path[i]->right; \
                                      } \
                                      if( eqt != NULL ) { \
                                          if( subcomparator == NULL ) { \
                                              SGLIB___BIN_TREE_FIND_MEMBER( type, s, eqt, left, right, comparator, s ); \
                                          } else { \
                                              SGLIB___BIN_TREE_FIND_MEMBER( type, s, eqt, left, right, subcomparator, s ); \
                                          } \
                                      } \
                                      if( s != NULL ) { \
                                          j = i+1; \
                                          it->path[j] = s; \
                                          it->pass[j] = 0; \
                                          it->pathi++; \
                                      } \
                                      it->pass[i]++; \
                                  } \
                              } \
                              if( it->pathi>0 && it->order == it->pass[it->pathi-1] ) { \
                                  it->currentelem = it->path[it->pathi-1]; \
                              } \
                          } \
                      } \
                      type *sglib__ ## type ## _it_init( struct sglib_ ## type ## _iterator *it, \
                                                         type *tree, \
                                                         int order, \
                                                         int ( *subcomparator )( type *, type * ), \
                                                         type *equalto ) { \
                          type *t; \
                          assert( it!=NULL ); \
                          it->order = order; \
                          it->equalto = equalto; \
                          it->subcomparator = subcomparator; \
                          if( equalto == NULL ) {  \
                              t = tree; \
                          } else { \
                              if( subcomparator == NULL ) { \
                                  SGLIB___BIN_TREE_FIND_MEMBER( type, tree, equalto, left, right, comparator, t ); \
                              } else { \
                                  SGLIB___BIN_TREE_FIND_MEMBER( type, tree, equalto, left, right, subcomparator, t ); \
                              } \
                          } \
                          if( t == NULL ) { \
                              it->pathi = 0; \
                              it->currentelem = NULL; \
                          } else { \
                              it->pathi = 1; \
                              it->pass[0] = 0; \
                              it->path[0] = t; \
                              if( order == 0 ) { \
                                  it->currentelem = t; \
                              } else { \
                                  sglib__ ## type ## _it_compute_current_elem( it ); \
                              } \
                          } \
                          return ( it->currentelem ); \
                      } \
                      type *sglib_ ## type ## _it_init( struct sglib_ ## type ## _iterator *it, type *tree ) { \
                          return ( sglib__ ## type ## _it_init( it, tree, 2, NULL, NULL ) ); \
                      } \
                      type *sglib_ ## type ## _it_init_preorder( struct sglib_ ## type ## _iterator *it, type *tree ) { \
                          return ( sglib__ ## type ## _it_init( it, tree, 0, NULL, NULL ) ); \
                      } \
                      type *sglib_ ## type ## _it_init_inorder( struct sglib_ ## type ## _iterator *it, type *tree ) { \
                          return ( sglib__ ## type ## _it_init( it, tree, 1, NULL, NULL ) ); \
                      } \
                      type *sglib_ ## type ## _it_init_postorder( struct sglib_ ## type ## _iterator *it, type * \
                                                                  tree ) { \
                          return ( sglib__ ## type ## _it_init( it, tree, 2, NULL, NULL ) ); \
                      } \
                      type *sglib_ ## type ## _it_init_on_equal( struct sglib_ ## type ## _iterator *it, \
                                                                 type *tree, \
                                                                 int ( *subcomparator )( type *, type * ), \
                                                                 type *equalto ) { \
                          return ( sglib__ ## type ## _it_init( it, tree, 1, subcomparator, equalto ) ); \
                      } \
                      type *sglib_ ## type ## _it_current( struct sglib_ ## type ## _iterator *it ) { \
                          return ( it->currentelem ); \
                      } \
                      type *sglib_ ## type ## _it_next( struct sglib_ ## type ## _iterator *it ) { \
                          sglib__ ## type ## _it_compute_current_elem( it ); \
                          return ( it->currentelem ); \
                      } \
\
                      static void sglib___ ## type ## _consistency_check_recursive( type *t, int *pathdeep, \
                                                                                    int cdeep ) { \
                          if( t==NULL ) { \
                              if( *pathdeep < 0 ) { *pathdeep = cdeep; }                                          \
                              else{ assert( *pathdeep == cdeep ); }                                     \
                          } else { \
                              if( t->left!=NULL ) { assert( comparator( t->left, t ) <= 0 ); }                                                            \
                              if( t->right!=NULL ) { assert( comparator( t, t->right ) <= 0 ); }                                                              \
                              if( SGLIB___GET_VALUE( t->bits ) == RED ) { \
                                  assert( t->left == NULL || SGLIB___GET_VALUE( t->left->bits )==BLACK ); \
                                  assert( t->right == NULL || SGLIB___GET_VALUE( t->right->bits )==BLACK ); \
                                  sglib___ ## type ## _consistency_check_recursive( t->left, pathdeep, cdeep ); \
                                  sglib___ ## type ## _consistency_check_recursive( t->right, pathdeep, cdeep ); \
                              } else { \
                                  sglib___ ## type ## _consistency_check_recursive( t->left, pathdeep, cdeep+1 ); \
                                  sglib___ ## type ## _consistency_check_recursive( t->right, pathdeep, cdeep+1 ); \
                              } \
                          } \
                      } \
\
                      void sglib___ ## type ## _consistency_check( type *t ) { \
                          int pathDeep; \
                          assert( t==NULL || SGLIB___GET_VALUE( t->bits ) == BLACK ); \
                          pathDeep = -1; \
                          sglib___ ## type ## _consistency_check_recursive( t, &pathDeep, 0 ); \
                      }

#define SGLIB_DEFINE_RBTREE_PROTOTYPES( type, left, right, colorbit, comparator ) \
    struct sglib_ ## type ## _iterator { \
        type *currentelem; \
        char pass[SGLIB_MAX_TREE_DEEP]; \
        type *path[SGLIB_MAX_TREE_DEEP]; \
        short int pathi; \
        short int order; \
        type *equalto; \
        int ( *subcomparator )( type *, type * ); \
    }; \
    extern void sglib___ ## type ## _consistency_check( type *t ); \
    extern void sglib_ ## type ## _add( type **tree, type *elem ); \
    extern int sglib_ ## type ## _add_if_not_member( type **tree, type *elem, type **memb ); \
    extern void sglib_ ## type ## _delete( type **tree, type *elem ); \
    extern int sglib_ ## type ## _delete_if_member( type **tree, type *elem, type **memb ); \
    extern int sglib_ ## type ## _is_member( type *t, type *elem ); \
    extern type *sglib_ ## type ## _find_member( type *t, type *elem ); \
    extern int sglib_ ## type ## _len( type *t ); \
    extern type *sglib_ ## type ## _it_init( struct sglib_ ## type ## _iterator *it, type *tree ); \
    extern type *sglib_ ## type ## _it_init_preorder( struct sglib_ ## type ## _iterator *it, type *tree ); \
    extern type *sglib_ ## type ## _it_init_inorder( struct sglib_ ## type ## _iterator *it, type *tree ); \
    extern type *sglib_ ## type ## _it_init_postorder( struct sglib_ ## type ## _iterator *it, type *tree ); \
    extern type *sglib_ ## type ## _it_init_on_equal( struct sglib_ ## type ## _iterator *it, type *tree, \
                                                      int ( *subcomparator )( type *, type * ), type *equalto ); \
    extern type *sglib_ ## type ## _it_current( struct sglib_ ## type ## _iterator *it ); \
    extern type *sglib_ ## type ## _it_next( struct sglib_ ## type ## _iterator *it ); \


#define SGLIB_DEFINE_RBTREE_FUNCTIONS( type, left, right, colorbit, comparator ) \
    SGLIB_DEFINE_RBTREE_FUNCTIONS_GENERAL( type, left, right, colorbit, comparator, 1, 0 )

/* ---------------------------------------------------------------------------- */
/* ---------------------------------------------------------------------------- */
/* -                          SUPPLEMENTARY DEFINITIONS                       - */
/* ---------------------------------------------------------------------------- */
/* ---------------------------------------------------------------------------- */

#define SGLIB___GET_VALUE( x )                          ( x )
#define SGLIB___SET_VALUE( x, value )                   {( x ) = ( value ); }
#define SGLIB_ARRAY_ELEMENTS_EXCHANGER( type, a, i, j ) {type _sgl_aee_tmp_; _sgl_aee_tmp_=( a )[( i )]; ( a )[( i )]= \
                                                             ( a )[( j )]; ( a )[( j )]= _sgl_aee_tmp_; }

#define SGLIB_SAFE_NUMERIC_COMPARATOR( x, y )           ( ( ( x )>( y ) ? 1 : ( ( x )<( y ) ? -1 : 0 ) ) )
#define SGLIB_SAFE_REVERSE_NUMERIC_COMPARATOR( x, y )   ( ( ( x )>( y ) ? -1 : ( ( x )<( y ) ? 1 : 0 ) ) )
#define SGLIB_FAST_NUMERIC_COMPARATOR( x, y )           ( (int)( ( x ) - ( y ) ) )
#define SGLIB_FAST_REVERSE_NUMERIC_COMPARATOR( x, y )   ( (int)( ( y ) - ( x ) ) )
#define SGLIB_NUMERIC_COMPARATOR( x, y )                SGLIB_SAFE_NUMERIC_COMPARATOR( x, y )
#define SGLIB_REVERSE_NUMERIC_COMPARATOR( x, y )        SGLIB_SAFE_REVERSE_NUMERIC_COMPARATOR( x, y )

#ifndef SGLIB_MAX_TREE_DEEP
#define SGLIB_MAX_TREE_DEEP           128
#endif

#ifndef SGLIB_HASH_TAB_SHIFT_CONSTANT
#define SGLIB_HASH_TAB_SHIFT_CONSTANT 16381   /* should be a prime */
/* #define SGLIB_HASH_TAB_SHIFT_CONSTANT 536870912*/   /* for large tables :) */
#endif

#endif /* _SGLIB__h_ */
